Watermarks have long been used in the printing industry to identify the source or origin of a document. Generally, a watermark appears as a faint pattern in an image, which is visible only when the original document is viewed in a particular manner. Unless a copyist had access to the watermarked paper, it would be difficult for him to reproduce the document without showing its unauthenticity. That is to say, without the paper on which the original image was originally printed, the copy should be readily detectable. However, as people move away from the use of watermarked papers for cost and other practical reasons, it is still necessary to identify the source or origin of a document image.
The introduction of the plain paper copier has resulted in a proliferation of paper copies of paper originals. A similar result is happening to electronic images, given the easy availability of digital scanners and a quick and widespread access to images throughout the Internet. It is now very difficult for the creator of an image to generate an electronic original, for which he can be assured that illegal copies will not be spread to third parties. The use of a digital watermark is a technology that aims to prevent that spread, by incorporating an identifying mark within the image that allows one to identify the source of the image in an electronic copy. It is important that the identifying mark not be disturbing or distracting to the original content of the image, while at the same time, allowing an easy identification of the source. The watermarks could be added either by the scanner or by the halftoning software.
Watermark identification may be accomplished by embedding a digital watermark in a digital or printed page that will identify the owner of rights to the image. In the past, these images have been produced and delivered in hard copy. In the future, these images will be distributed mainly in digital form. Therefore, image identification will have to work for both hard copy and digital image forms.
Watermarking can take two basic forms, visible or perceptible and invisible or imperceptible. Visible watermarks are marks such as copyright logos or symbols or logos that are imprinted into the digital or printed image to be distributed. The presence of the watermark is made clearly visible in the image in a way that makes it difficult to remove without damaging the image. The presence of the visible watermark does not harm the usefulness of the image, but it prevents the image from being used without permission. However, visible watermarks may interfere with the use of the image or with the image aesthetics. The visible watermark is also a potential target for fraud, in that it is possible for a fraudulent copier of the image to identify the location of the watermark and attempt to reproduce the image without the watermark.
Invisible watermarks are marks such as copyright symbols, logos, serial numbers, etc. that are embedded into digital or printed images in a way which is not easily discernible to the unaided eye. At a later time, the information embedded in these watermarks can be derived from the images to aid identification of the source of the image, including the owner and the individual to whom the image is sold. Such watermarks are useful for establishing ownership when ownership of an image is in dispute. They will be less likely to be useful as a deterrent to the theft of the image. While either or both visible or invisible watermarks are desirable in an image, they represent different techniques for either preventing copying or detecting copying.
Several conventional techniques for rendering and/or retrieving digital watermarks have been proposed or implemented. For example, a correlation-based stochastic screening methodology for embedding the retrieving invisible watermarks in printed documents has been proposed. In such conventional approaches, a well-designed stochastic screen that appears similar to a pattern with some evenly distributed dots can generate the halftone output. By varying the density of the black (or white) dots, different gray levels may be simulated, even though the halftone output is essentially only black-and-white. Certainly, there are many possible different “random” distributions, which can function equally as the visual effect of half-toning is concerned.
FIG. 1 illustrates a group of conventional halftone patterns for illustrative purposes. For example, in FIG. 1 three halftone patterns 102, 104, 106, respectively labeled as (A), (B), and (C) are depicted, which show little difference unless they are compared closely. A quick comparison of two dot distributions can be conducted by the overlay one pattern on another as indicated in FIG. 1. The overlay of the distribution (A) on (B) shows that there is no difference between the two distributions as indicated by pattern 108, while the overlay of (A) on (C) yields a quite different result as indicated by pattern 110.
In other words, it can be concluded that the distributions of (A) and (B) are highly correlated (i.e., they are identical in this particular case), while (A) and (C) are much less correlated, or almost uncorrelated. Mathematically, the overlaying comparison of two digital binary images is equivalent to a pixel-wise AND operation. It is not difficult to see that a XOR (i.e., exclusive “or”) logical operation may provider a stronger visual difference, considering that the XOR result of (A) and (B) as indicated by pattern 112 (i.e., two identical binary patterns) is merely a pattern with a uniform value one. The pattern 114 is based on a XOR result of (A) and (C), which is visually much stronger than that of pattern 112.
FIG. 2 illustrates the basic concept of embedding watermark into a halftone image. Consider a halftone pattern (D) composed of two partitions: part one is cut off from the distribution (B) depicted in FIG. 1 and part two is from the distribution (C) also depicted in FIG. 1. Thus, the first partition of (D) is represented by pattern 202, while the second partition of (D) is represented by pattern 204. Therefore, overlay of the distribution (A) as indicated by pattern 206 on the composed pattern (D) as indicated by pattern 208 shows a strong contrast between the correlated partition and the uncorrelated one.
With a simple cut-and-paste process, however, the watermark might be visible through the “seam” between two partitions, as shown below by careful examining the pattern (D) (i.e. pattern 208). A logical AND combination of (A) and (D) results in pattern 210, while a logical XOR of (A) and (D) results in pattern 212. While such kind of “visible” watermarks might be acceptable for some applications, invisible watermarks are certainly more desirable for security and many other purposes including maintaining high image quality.
It was previously proposed to make the watermark truly invisible by “smearing out the seam” using a special screen design process. An invisible watermark, such as a letter or a simple binary pattern, can be embedded into a stochastic screen, which can be utilized as a normal halftone screen, and no further watermark embedding is needed during halftoning and printing. The drawback of this approach is that the watermark pattern is fixed and limited to relatively a small size and simple shapes due to the constraints of the current design processes for stochastic screens. A method for utilizing two correlated stochastic screens to embed variable data into images at the run time has also been proposed.
Thus, such conventional correlation-based stochastic screening methods can provide a practical approach to embed watermarks in documents for both their digital formats and printed hardcopies. Stochastic screening, the single-pixel-based halftone method, however, is mainly utilized for inkjet printers and is practically unsuitable to xerographic printers. For most printing products, to embed digital watermarks into a halftone image at a high resolution and a high quality, a methodology based on manipulating ordered cluster screens is required. Such a methodology, including related systems and devices, has to date not been designed or implemented.
There are also many other digital watermark methods proposed for electronic and printed images. Most approaches for embedding watermarks into halftone images, however, are based on manipulating individual pixels, such as by design of special stochastic screens or by modifying error diffusion halftone methods. In some the same manner, the glyph method applied to halftone images also falls into this category.
Due to the nature of xerographic printing, however, that is the technique for the majority of printing products, single-pixel-based halftoning methods, including stochastic screening and error diffusion, have limited applications. Instead, ordered cluster halftone screens are still the only choice of halftone implementation equipped or supported by most printers. Many existing digital watermark methods work well on digital formats of images but fail badly in detection of embedded watermark information from hardcopies, unless the images are printed in much lower resolutions or the embedded information is reduced to fit in much smaller capacities. There is a strong demand for digital watermark methodologies and systems, which can embed information into printed documents using ordered halftone screens.